#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int g[N][N]; //邻接矩阵
bool st[N];
int q[N] , hh , tt = -1; //BFS队列
void add(int a , int b , int c)
{
    g[a][b] = c;
}
void dfs(int a)
{
    printf("%d ",a);
    st[a] = true;
    for(int i = 0 ; i <= 7 ; ++i)
    {
        if(g[a][i] == 1 && !st[i]) dfs(i); 
    }
}
void bfs(int a)
{
    memset(st,0,sizeof st);
    q[++tt] = a;
    st[a] = true;
    while(hh <= tt)
    {
        printf("%d ",q[hh]);
        for(int i = 0 ; i <= 7  ; ++i)
        {
            if(g[q[hh]][i] == 1 && !st[i])
            {
                st[i] = true;
                q[++tt] = i;
            }
        }
        ++hh;
    }
}
int main()
{
    add(0,1,4);
    add(0,3,5);
    add(1,2,1);
    add(2,0,);
    add(2,3);
    add(1,4);
    add(4,9);
    add(2,5);
    add(5,3);

    for(int i = 0 ; i <= 7 ; ++i)
    {
        for(int j = 0 ; j <= 7 ; ++j)
        {
            printf("%d ",g[i][j]);
        }
        printf("\n");
    }
    printf("DFS:\n");
    dfs(0);
    printf("\n");
    printf("BFS:\n");
    bfs(0);
    return 0;
}